#ifndef _TREE_C
#define _TREE_C

#include "_Tree.h"

/* Constructor */
void 
initTree(Tree *initThis, int (*compareObject)(const void *objectOne, 
                                              const void *objectTwo))
{
    if(compareObject == NULL) {
        initThis->compare = &__genericCompare;
    } else {
        initThis->compare = compareObject;
    }

    initThis->root = NULL;
    initThis->length = 0;
}

/* Destructor */
/* Returns an Array of all elements that deleteThis holds. */
/* 
 * TODO: Make this iterative.
 * Right now it essentially is recursive, instead of using the callstack, 
 * it just uses a Stack.
 */
Array
deleteTree(Tree *deleteThis)
{
    Array toReturn;
    _Chain stack;
    _Node *temp = NULL;
    _Node *toDelete = NULL;
    size_t index = 0;

    if(deleteThis != NULL) {
        initArray(&toReturn, deleteThis->length);
        _initChain(&stack, _TYPE_CHAIN);

        temp = deleteThis->root;
        while(1) {
            if(temp != NULL) {
                StackPush(&stack, temp);
                temp = temp->leftNode;
            } else {
                if(stack.length == 0) {
                    break;
                }

                temp = _ChainPopFront(&stack);
                ArraySet(&toReturn, index, temp->data);
                index++;
                toDelete = temp;
                temp = temp->rightNode;
                _deleteNode(toDelete);
            }
        }

        _deleteChain(&stack);
    }

    return toReturn;
}

/*
 * Returns the location in memory, of the pointer which points to 
 * (or should/will point to) the Node which/will contain(s) getThis.
 */
_Node **
__TreeNodeGet(Tree *t, void *getThis)
{
    _Node *temp = NULL;
    _Node *tempParent = NULL;
    int compareResult;

    if(t->root == NULL) {
        return &t->root;
    } else {
        temp = t->root;

        while(temp != NULL) {
            compareResult = t->compare(getThis, temp->data);

            if(compareResult < 0) {
                if(temp->leftNode == NULL) {
                    return &(temp->leftNode);
                } else {
                    tempParent = temp;    
                    temp = temp->leftNode;
                }
            } else if(compareResult> 0) {
                if(temp->rightNode == NULL) {
                    return &(temp->rightNode);
                } else {
                    tempParent = temp;
                    temp = temp->rightNode;
                }
            } else {
                if(tempParent == NULL) {
                    return &(t->root);
                } else {
                    if(tempParent->leftNode == temp) {
                        return &(tempParent->leftNode);
                    } else {
                        return &(tempParent->rightNode);
                    }
                }
            }
        }
    }

    return NULL;
}

int
TreeAdd(Tree *t, void *addThis)
{
    _Node **parentNode = __TreeNodeGet(t, addThis);
    _Node *toAdd = _newNode(addThis);

    if(*parentNode == NULL) {
        *parentNode = toAdd;
        t->length++;
        return 1;
    } else {
        _deleteNode(toAdd);
        return 0;
    }
}

int
TreeContains(Tree *t, void *findThis)
{
    _Node **parentNode = __TreeNodeGet(t, findThis);

    if(*parentNode != NULL) {
        return 1;
    } else {
        return 0;
    }
}

void *
TreeExtract(Tree *t, void *extractThis)
{
    _Node **parentNode = __TreeNodeGet(t, extractThis);
    _Node *temp = NULL;
    _Node *bottomNode = NULL;
    void  *toReturn = NULL;

    size_t leftHeight;
    size_t rightHeight;

    if(*parentNode != NULL) {
        temp = *parentNode;

        /* 
         * Determines the height of the subtrees and 
         * rotates the tree depening on which one is taller.
         */
        leftHeight = __height(temp->leftNode);
        rightHeight = __height(temp->rightNode);

        if(leftHeight > rightHeight) {
            *parentNode = temp->leftNode;
            bottomNode = __bottomRight(temp->leftNode);

            if(bottomNode != NULL) {
                bottomNode->rightNode = temp->rightNode;
            }
        } else {
            *parentNode = temp->rightNode;
            bottomNode = __bottomLeft(temp->rightNode);
            
            if(bottomNode != NULL) {
                bottomNode->leftNode = temp->leftNode;
            }
        }

        toReturn = temp->data;
        _deleteNode(temp);

        t->length--;

        return toReturn;
    }

    return NULL;
}

/* TODO: Make this iterative */
size_t
__height(_Node *root)
{
    size_t leftHeight = 1;
    size_t rightHeight = 1;

    if(root != NULL) {
        leftHeight += __height(root->leftNode);
        rightHeight += __height(root->rightNode);

        return _MAX(leftHeight, rightHeight);
    } else {
        return 0;
    }
}

/* TODO: Make this iterative */
_Node *
__bottomLeft(_Node *root)
{
    if(root != NULL) {
        if(root->leftNode != NULL) {
            return __bottomLeft(root->leftNode);
        } else {
            return root;
        }
    }

    return root;
}

/* TODO: Make this iterative */
_Node *
__bottomRight(_Node *root)
{
    if(root != NULL) {
        if(root->rightNode != NULL) {
            return __bottomRight(root->rightNode);
        } else {
            return root;
        }
    }

    return root;
}

#endif
